\chapter{Incorporating High-Level Synthesis in Physical Planning of\\ Three Dimensional (3D)
ICs}\label{chapter:3d}

Three-dimensional (3D) circuit integration is a promising technology to
alleviate performance and power related issues raised by interconnects in
nanometer CMOS. Physical planning of three-dimensional integrated circuits is
substantially different from that of traditional planar integrated circuits,
due to the presence of multiple layers of dies. To realize the full potential
offered by three-dimensional integration, it is necessary to take physical
information into consideration at higher-levels of the design abstraction for
3D ICs. This chapter proposes an incremental system-level synthesis framework
that tightly integrates behavioral synthesis of modules into the layer
assignment and floorplanning stage of 3D IC design. Behavioral synthesis is
implemented as a sub-routine to be called to adjust
delay/power/variability/area of circuit modules during the physical planning
process. Experimental results show that with the proposed
\emph{synthesis-during-planning} methodology, the overall timing yield is
improved by 8\%, and the chip peak temperature reduced by 6.6
$^{\tiny\textrm{o}}$C, compared to the conventional
\emph{planning-after-synthesis} approach.

\section{Introduction}\label{sec:intro}

To further improve integration density and to tackle the interconnect challenge
as technology continues scaling, researchers have been pushing forward
three-dimensional (3D) IC stacking~\cite{Davis2005,Xie2006}. In a 3D IC,
multiple device layers are stacked together with direct vertical interconnects
through substrates. 3D ICs offer a number of advantages over traditional
two-dimensional (2D) design, such as (1) higher packing density and smaller
footprint; (2) shorter global interconnect due to the short length of
through-silicon vias (TSVs) and the flexibility of vertical routing, leading to
higher performance and lower power consumption of interconnects; (3) support of
heterogenous integration: each single die can have different technologies.

Conventional thinking on HLS for 3D ICs focused on such a
\emph{planning-after-synthesis} flow that HLS was done first to generate the
block-level (function unit) implementation of circuits, and 3D integration is
used to put together blocks such as adders and multipliers. For any
unsatisfactory in the integration, HLS is redone and then physical design
follows. The problem here is that these blocks might be very small in size and
this leads to a fine granularity in 3D integration. The physical planning
(layer assignment and floorplanning) at this granularity might be impractical
in real designs for the following reasons: (1) Very fine-grain integration of
3D ICs splits modules to different layers and creates more inter-layer
connections, which is not desirable as the delay and area overheads on
through-silicon vias (TSVs) is not negligible. (2)In typical designs there
would be thousands of such function-level blocks. Optimal physical planning for
such a input scale could be challenging and time-consuming, which complicates
the early-stage design exploration and increase time to market of a design.

A new thinking is to bring 3D integration to a higher level, to address the
integration of modules in a system, instead of function units inside a module.
In this way, the combination of HLS and 3D IC design might be a different
story. HLS is implemented as a sub-routine to be called to adjust
delay/power/area of circuit modules during the physical planning process. In
this \emph{synthesis-during-planning} flow, HLS is first performed to estimate
the delay, power and area of architectural modules in the system, such as ALU,
FPU, \emph{etc}. Then 3D partition and floorplanning are done to integrate
these modules, and timing/power/variability/thermal analysis are performed on
the planned results. If the constrains are not met, the modules on critical
paths or hot spots are picked out and sent back to HLS. In this iteration, HLS
is to re-explore the design space of such modules on certain directions and to
generate new implementations with different (delay, power, variability, area)
properties. Modules with new internal architectures provide new opportunities
for the 3D integration and therefore it's likely to improve the design towards
the constraints. With multiple iterations it will generate designs that are
ready for low-level implementation. This flow can avoid the problem and
concerns on very fine-granularity 3D integration, and can be done quickly to
get a reasonable 3D implementation in the early stage of a design process.

\section{Related Work}\label{related}
Most of previous work on layout-aware high-level synthesis only handled 2D
circuits~\cite{KJLJ01,SHSS03}. These approaches typically use a loosely coupled
independent floorplanner for physical estimation. Gu \emph{et.
al}~\cite{GWDZ05} proposed a incremental exploration framework of the combined
physical and behavioral design space, which enables maintaining physical-level
properties across consecutive physical estimations during behavioral synthesis.
Tightly integrating the high-level and layout-level phases of synthesis is
necessary to ensure convergence of the synthesis flow.

Only a few previous work have been reported on high-level synthesis aimed at 3D
layouts. Mukherjee \emph{et. al}~\cite{MV04} has addressed the layer assignment
problem during high-level synthesis for 3D ICs. However, their approach
separates the high-level synthesis from the layer assignment step, and the 0-1
integer linear programming formulation in their approach is typically unable to
explore large design space due to the computation complexity. Krishnan
\emph{et. al}~\cite{KK07} proposed a 3D-layout aware binding algorithm for
high-level synthesis of 3D ICs. While these work addressed the synthesis of 3D
IC in various aspects, the major drawback is the granularity of the objects for
physical planning. Tackling the physical planning problem at functional blocks
level would be trivial as we stated in the previous section.

Our work in this chapter is substantially different from the existing ones, in
such a way that physical planning at the granularity of modules operates in an
outer loop, while HLS is employed as a refining tool in the inner loop to
optimize the delay/power/area of modules, so that the modules can be fit better
in the physical planning of 3D ICs.

\section{The Problem Definition}\label{sec:problem}


\begin{figure}
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.6\textwidth]{Chapter-6/Figures/designspace.pdf}
  \caption{The design space of a module in high-level synthesis}\label{fig:designspace}
 % \vspace{-10pt}
\end{figure}


This section introduces preliminaries on high-level synthesis and 3D physical
planning, and then presents the problem formulation.

\subsection{Design Space Exploration in High-Level Synthesis}

The resource library used in high-level synthesis consists of hardware units
with different delay and area properties, which make it possible to perform
design exploration to get more optimized result during the synthesis process.
Figure~\ref{fig:designspace} shows the design space exploration for a specific
module used in high-level synthesis. \texttt{ARCH I-III} denotes different
architectural implementations of the module with the same functionality, while
the black squares inside each architecture shows the design points with
different module-level and circuit-level optimizations (multi-Vth/Vdd, gate
sizing, \emph{etc}.), which lead to different delay and power values of the
same architecture. Therefore, given the delay constraint shown in
Figure~\ref{fig:designspace}, there are two architectures available and each
architecture has two viable design options. The synthesis tool can choose
between these options for a best fit of all design considerations.



\subsection{3D Physical Planning}

Physical planning is a key step in 3D IC design. It usually involves layer
assignment and floorplanning of modules on each layer. Layer assignment, which
is unique in 3D IC design, assigns blocks and modules to different layers in
order to balance the area split, to mitigate the thermal crisis, as well as to
reduce the interconnect wirelength. Figure~\ref{fig:3dfp} shows the physical
planning process for a 3D microprocessor. During the planning process, modules
can be moved around within a layer as well as between layers, to achieve the
best performance in terms of delay/power/area/\emph{etc}. A coarse-grain
physical planning methodology can generate balanced assignment and placement of
modules at the early stage of the design process, and provide confidence and
guidance for the succeeding design steps.

\begin{figure}
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.5\textwidth]{Chapter-6/Figures/3dfp.pdf}
  \caption{3D physical planning including layer assignment and floorplanning}\label{fig:3dfp}
%  \vspace{-10pt}
\end{figure}


\subsection{Problem Formulation}
During 3D physical planning, several operations can be performed to change the
location, layer assignment and aspect ratio of any module. However, the
delay/power/area of such modules are fixed, leading to a limited design space.
Meanwhile, high-level synthesis can generate architectures and design points of
a give specification with different delay/power/area values. Therefore, if
high-level synthesis can be incorporated into the physical planning process,
the design space will be significantly enlarged and the quality of the design
decision will be greatly improved. With high-level synthesis as a tuning knob
of each modules in the design, a framework with two levels of optimization
loops can be established, in which the physical planning serves as the outer
loop and evaluates all potential movements, and high-level synthesis acts as a
fine tuning tool to facilitate the movements. Within such a framework, several
design considerations including performance, process variability and thermal
efficiency of 3D ICs can be effectively addressed:

\vspace{5pt}\noindent\textbf{A. Mitigating the Impact of Process Variations}

\noindent CMOS process variability is a major challenge in deep-submicron SoC
designs. The variations in transistor parameters are complicating both timing
and power consumption prediction. Chapter 4 has shown that different
architectural implementations of the same function modules, might have
different immunity to process variability. Consequently, architectural
components such as ALU will exhibit similar behavior when they are built up
with these circuit modules. Therefore, besides delay and power, the variability
becomes a new metric to explore and to optimize during higher levels of the
design hierarchy.

Researchers have then proposed optimization techniques in behavioral or
high-level synthesis to reduce the variability of synthesized results, with the
price of increased power or silicon area~\cite{HLS:Jung07, HLS:Wang082,
HLS:Greg09}. These techniques can mitigate the impact of process variations at
the early stage of a design flow. However, most of these optimizations are
physical-unaware -- the work on high-level is unable to address the impact of
interconnects and spatial correlations of process variability. Combining
high-level synthesis and physical planning will lead to an effective way to
address the process variability of 3D ICs. In our proposed framework, after the
initial physical planning is done, the interconnect delays are extracted and
the process variations of all components are re-evaluated with the updated
spatial correlations. With such information, the near-critical components can
be identified, and HLS is then called to optimize such modules to reduce the
variability. The optimization will result in alternatives with different
power/area, and these may violate the delay/power/thermal constraints so a new
iteration of physical planning is required.

To bring the process-variation awareness to the high-level synthesis flow, we
first introduce a new metric called \emph{Parametric Yield}. The parametric
yield is defined as the probability of the synthesized hardware meeting a
specified constraint $Yield = P(Y \leq Y_{max})$, where $Y$ can be delay or
power. We assume that each architectural blocks are separately by registers.
Given the clock cycle time $t_{CLK}$, the timing yield of the entire system,
$Yield_{t}$ is defined as:
\begin{equation}\label{eq:C6-tyield}%\scriptsize
Yield_{t}=P(t_1 \leq t_{CLK}, t_2\leq t_{CLK},\ldots,t_n\leq t_{CLK})
\end{equation}
where $P()$ is the probability function, $t_1, t_2,\ldots,t_n$ are the arrival
time distributions of each architectural block $B_1, B_2,\ldots,B_n$,
respectively.

In each iteration, we use the model presented in~\cite{PV:ABZ03a} to model the
spatial correlations of the process variability. As shown in
Fig.~\ref{fig:pvmodel}, an independent random variable $L_{l,r}$ is associate
with each region $(l, r)$ to represent a component of the total process
variation. The total intra-die variation of a given block will be the sum of
$L_{l,r}$ variables corresponding to the $(l,r)$ regions that intersect with
the block. Such spatial correlations are then fed to a gate-level statistical
timing analysis tool to recalculate the yield of each architectural block.

\begin{figure}
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.5\textwidth]{Chapter-6/Figures/pvmodel.pdf}
  \caption{The process variability model with spatial correlation~\cite{PV:ABZ03a}.}\label{fig:pvmodel}
%  \vspace{-10pt}
\end{figure}


\vspace{5pt}\noindent\textbf{B. Improving Thermal Efficiency}

\noindent Heat dissipation is one of the key challenges in the design of 3D
ICs, due to the stacking of multiple active layers and the improved logic
density. Therefore, the thermal efficiency problem has to be addressed from the
very beginning of the 3D IC design. In our proposed physical planning
framework, a temperature estimator could be integrated into the flow to
evaluate the temperature profile of the design after any optimistical move. At
each iteration, the framework will identify the modules with hot spots. Such
modules will be moved around the chip for a better head conduction or be
replaced with their alternatives. At this point, the design space of such
modules could be explored, and candidates with lower power consumption, thus
lower heat dissipation could be chosen as the replacement. After the movement
or replacement of these critical modules, a new iteration will be initiated to
optimize the other modules in order to meet the design constraints.

For quick temperature estimation, we model 3D ICs as resistor-capacitor
structures in a thermal RC model similar to~\cite{Huang2006}. For a
microarchitectural unit, heat conduction to the thermal package and to
neighboring units are the dominant mechanisms that determine the temperature.
The RC model consists of a vertical and a lateral convection model.
Figure~\ref{fig:tsvfarmblock} shows the block level RC modeling, where each
modules is modeled as a block with its power dissipation and thermal
resistance. The vertical thermal resistance ($R_V$) captures heat flow from one
layer to the next, moving from the source die through the package. The lateral
thermal resistance ($R_L$) captures heat diffusion between adjacent blocks
within a layer, and from the edge of one layer into the periphery of the next
area. The temperature of each block can then be estimated as:
\begin{equation}\label{eq:temp}
\small
\left[ \begin{array}{c}
T_1 \\
T_2 \\
\vdots \\
T_n
\end{array} \right]
=
\left[ \begin{array}{cccc}
R_{11} & R_{12} & \ldots & R_{1n}\\
R_{21} & R_{22} & \ldots & R_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
R_{n1} & \ldots & \ldots & R_{nn} \\
\end{array} \right]
\times
\left[ \begin{array}{c}
P_1 \\
P_2 \\
\vdots \\
P_n
\end{array} \right]
.
\end{equation}
where $T_{1\ldots n}$ and $P_{1\ldots n}$ denotes the temperature and power
consumption values for blocks $1\ldots n$, respectively. $\mathbf{R}=R_{1\ldots
n,1\ldots n}$ is the transfer matrix built from $R_V$ and $R_L$ of each block.

\begin{figure}
\centering
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.55\textwidth]{./Chapter-6/Figures/tsvfarm.pdf}\\
  \caption{Block mode thermal RC modeling for 3D ICs.}\label{fig:tsvfarmblock}
%  \vspace{-10pt}
\end{figure}

 With the proposed fast temperature estimator, the physical planning flow
is able to address the thermal issue by iteratively identifying the hot spots
and optimizing the corresponding modules through design space exploration,
creating a balanced thermal profile for the whole IC stack.

\section{Experiment Analysis and Case Studies}\label{sec:C6-analysis}

In this section, we first present the experiment results of the design space
exploration for delay/power/variability in high-level synthesis, and then
demonstrate the effectiveness of our proposed \emph{synthesis-during-planning}
approach on several benchmarks.

\subsection{Results for Design Space Exploration in High-Level Synthesis}

With the variation-aware multi-$V_{th}/V_{dd}$ resource library characterized
in Chapter 4, we preform design space exploration for power reduction on a set
of industrial high-level synthesis benchmarks. The dynamic power consumption of
function units is estimated by Synopsys \emph{Design Compiler} with
multi-$V_{th}/V_{dd}$ technology libraries generated by \emph{Liberty NCX}. In
this work with FreePDK 45nm technology, the dynamic power is about 2 times of
the mean leakage power.



\begin{figure}[!btp]
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.7\textwidth]{Chapter-6/Figures/result3.pdf}
 %   \vspace{-10pt}
  \caption{Design space exploration on timing
and power yield of the synthesized design.}\label{fig:C6-result3}
%    \vspace{-10pt}
\end{figure}

Fig.~\ref{fig:C6-result3} shows the power reduction of the synthesized design
compared with conventional single-voltage design. The average power reductions
against conventional worst-case based design, under timing yield constraints
99\%, 95\% and 90\% are 11.7\%, 21.0\% and 27.2\%, respectively. It is clearly
shown that, the power reduction largely depends on how much timing yield loss
is affordable for the design. This testifies the necessity of design space
exploration for a well balanced timing yield and power trade-off.

\subsection{Results of the Incorporated 3D Physical Planning Flow}
\begin{table*}[tbh]
\caption{Physical planning results of 3D architecture}
\label{tab:tab2}\vspace{-5pt} \scriptsize
\begin{center}
%\setlength{\tabcolsep}{0.2mm}
\begin{tabular}{c|c|c|c|c|c||c|c|c|c|c} \hline \hline
{\bf {Circuit}} & \multicolumn{5}{|c||} {\bf{Planning-after-Synthesis}} & \multicolumn{5}{|c} {\bf{Synthesis-during-Planning}} \\ \cline{2-11}
&\multicolumn{1}{|c|} {wire} & {area} & {peakT}
& {timing} & {run}
&\multicolumn{1}{|c|} {wire} & {area} & {peakT}
& {timing} & {run}\\

&\multicolumn{1}{|c|} {($um$)} & {($mm^2$)} & {} & {yield} & {T (s)}
&\multicolumn{1}{|c|} {($um$)} & {($mm^2$)} & {} & {yield} & {T (s)}\\\hline

$Alpha$  &210749 &15.49  &126.01 &85.2\% &363
         &210833 &15.44  &117.48 &94.3\% &2718\\\hline

$ami33$  &27911  &0.613  &164.60 &92.7\% &113
         &27435  &0.625  &154.65 &98.8\% &1165\\ \hline

$ami49$  &547491 &18.55  &130.22 &90.1\% &386
         &52090  &18.72  &124.19 &95.7\% &4590\\ \hline

$hp$     &124819  &4.45  &125.67 &88.7\% &16
         &119863  &4.51  &120.39 &96.5\% &871\\ \hline

$xerox$  &297440  &9.76  &127.21 &91.3\% &17
         &295768  &9.60  &119.64 &97.2\% &1615\\ \hline\hline

$Average$&1 &1  &1 &1 &1
         &0.99 &1.00  &0.95 &1.08 &12.24\\ \hline\hline

\end{tabular}
\end{center}
%\vspace{-0.5cm}
\end{table*}

For the experiments on 3D physical planning, we use an Alpha-like detailed
microprocessor with the IVM verilog model~\cite{URL:IVM}, as well as several
MCNC benchmarks. The processor model is synthesized with FreePDK 45nm
technology library. The power density of each module is set between $1-5
W/mm^2$. The designs are split into two layers of a 3D IC, and the delay and
area overhead on through-silicon-vias (TSVs) are not accounted for the sake of
brevity. The physical planning flow is implemented in C++ and experiments are
conducted on a Linux workstation with a 3.2GHz dual-core CPU.

We compare the results with the conventional \emph{planning-after-synthesis}
flow as shown in Table~\ref{tab:tab2}. The left half of the table displays the
total wirelength, the chip footprint, the peak temperature of the chip, and the
overall timing yield for the conventional approach, while the right half shows
the results for our proposed approach, respectively. The cost factors are set
in order that the total wirelength and the chip footprint are kept unchanged,
while the rest two factors are to be optimized. Results over the benchmarks
show that the proposed \emph{synthesis-during-planning} approach can reduce the
chip peak temperature by 6.6~$^{\tiny\textrm{o}}$C on average, and improve the
overall timing yield by 8\%, without causing overheads on wirelength or chip
area. The benefits come from the fact that low-power or low-variability
alternatives of modules which fit the needs best, are placed on the critical
spots, while the slightly expensive modules in terms of power or area, are
introduced at non-critical locations. This demonstrates the effectiveness and
necessity that extra high-level design space exploration is used during the
physical planning of 3D IC design. Due to the iterative optimization, the run
time of the proposed approach increases by about 10 times, but is still in an
acceptable range for a design flow starting from system-level specifications
and generating placed RTL netlists.

\section{Summary}

This chapter proposed an incremental system-level synthesis framework that
 integrates behavioral synthesis of modules into the layer assignment
and floorplanning stage of 3D IC design. Behavioral synthesis is implemented as
a sub-routine to be called to adjust delay/power/variability/area of circuit
modules during the physical planning process. Experiment results show that the
proposed synthesis-during-planning approach outperforms the conventional
planning-after-synthesis approach in reducing the chip power consumption, chip
area and the impact of process variability.
